class Solution(object):
    def climbStairs(self, n):
        """
        :type n: int
        :rtype: int
        """
        """ 
        动规题目  
        首先是确定状态: 最后一步可能是 由跨一步来 或者两步来
        所以 子问题 是 最后前n-1步的 总数量
        
        转移方程：d[i-1]+d[i-2]  跨一步，跨两步的和
        
        边界d[0] = 0,d[1]=0  d[2]=2 因为 n要大于等于2 才可以走两步
        """


        # d = [0,1,2]
        # if n < 3:
        #     return d[n]
        # for i in range(3,n+1):
        #     h = d[i-1]+d[i-2]
        #     d.append(h)
        # return d[-1]

        if n == 0:
            return 0
        f = [0] * (n + 1)
        f[0] = 0
        f[1] = 1
        if n > 2:
            f[2] = 2
        for i in range(3, n+1):
            f[i] = f[i - 1] + f[i - 2]
        print(f)
        return f[-1]


n=3
s=Solution()
m =s.climbStairs(n)
print(m)